package com.fps.webshop.question.question0001_0099;

/**
 * 10. 正则表达式匹配
 * 
 * 给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。
 * 
 * '.' 匹配任意单个字符
 * '*' 匹配零个或多个前面的那一个元素
 * 
 * 所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。
 * 
 * 示例 1：
 * 输入：s = "aa" p = "a"
 * 输出：false
 * 解释："a" 无法匹配 "aa" 整个字符串。
 * 
 * 示例 2:
 * 输入：s = "aa" p = "a*"
 * 输出：true
 * 解释：因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。
 * 
 * 示例 3：
 * 输入：s = "ab" p = ".*"
 * 输出：true
 * 解释：".*" 表示可匹配零个或多个（'*'）任意字符（'.'）。
 * 
 * 示例 4：
 * 输入：s = "aab" p = "c*a*b"
 * 输出：true
 * 解释：因为 '*' 表示零个或多个，这里 'c' 为 0 个, 'a' 被重复一次。因此可以匹配字符串 "aab"。
 * 
 * 示例 5：
 * 输入：s = "mississippi" p = "mis*is*p*."
 * 输出：false
 * 
 * 提示：
 * 		0 <= s.length <= 20
 * 		0 <= p.length <= 30
 * 		s 可能为空，且只包含从 a-z 的小写字母。
 * 		p 可能为空，且只包含从 a-z 的小写字母，以及字符 . 和 *。
 * 		保证每次出现字符 * 时，前面都匹配到有效的字符
 */
public class Question010 {

	/**
	 * 第一次提交，完全不行，没过
	 * 提交结果	执行用时	内存消耗	语言		提交时间				备注 
	 *
	 */
	public static boolean isMatch1(String s, String p) {
		int startA = 0;
		int startB = 0;
		char[] sA = s.toCharArray();
		char[] sB = p.toCharArray();
		Character tmpC = ' ';
		int tmpI = 0;
		
		while (startA<s.length()&&startB<p.length()) {
			if(sA[startA]==sB[startB]) {
				startA++;
				startB++;
			}else {
				//不相等
				if(sB[startB]=='.') {
					//.的情况
					startA++;
					startB++;
				}else if(sB[startB]=='*') {
					//当前是*，和之前一样
					if(sB[startB-1]==sA[startA]||sB[startB-1]=='.') {
						if(tmpC == sB[startB-1]) {
							tmpI++;
						}else {
							tmpC = sB[startB-1];
							tmpI = 1;
							tmpI++;
						}
					}else if(sB[startB-1]==sA[startA-1]) {
						startB++;
						continue;
					}else {
						break;
					}
					
					if((startA+1)<s.length()&&sA[startA+1]==sA[startA]) {
						
					}else {
						startB++;
					}
					startA++;
				}else if((startB+1)<p.length()&&sB[startB+1]=='*') {
					//后面有*的情况
					startB++;
					startB++;
				}else {
					if((sB[startB]==tmpC||tmpC=='.')&&tmpI>0) {
						tmpI--;
						startB++;
					}else {
						//完全不匹配
						break;
					}
				}
			}
		}
		
		while(startB!=p.length()) {
			if(sB[startB]=='*'&&(sB[startB-1]==sA[startA-1]||sB[startB-1]=='.')) {
				if(tmpC == sB[startB-1]) {
					tmpI++;
				}else {
					tmpC = sB[startB-1];
					tmpI = 1;
				}
				startB++;
			}else if((startB+1)<p.length()&&sB[startB+1]=='*') {
				//后面有*的情况
				startB++;
				startB++;
			}else if(sB[startB]==tmpC&&tmpI>0) {
				tmpI--;
				startB++;
			}else {
				//完全不匹配
				break;
			}
		}
		if(startA==s.length()&&startB==p.length()) {
			return true;
		}else {
			return false;
		}
    }
	
	/**
	 * 官方解答
	 * 详解：Question010_01.jpg
	 * 
	 * 提交结果	执行用时	内存消耗	语言		提交时间				备注 
	 * 通过 		2 ms	36.9 MB	Java	2021/08/20 14:41
	 * 
	 * 执行用时：2 ms, 在所有 Java 提交中击败了95.96%的用户
	 * 内存消耗：36.9 MB, 在所有 Java 提交中击败了88.62%的用户
	 */
    public static boolean isMatch(String s, String p) {
        int m = s.length();
        int n = p.length();

        boolean[][] f = new boolean[m + 1][n + 1];
        f[0][0] = true;//f[0][0]代表s和p均为空字符串，f[1][1]代表s和p的第一个字符（即在s和p中下标为0的字符）
        for (int i = 0; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (p.charAt(j - 1) == '*') {//p的第j个字符为*
                    f[i][j] = f[i][j - 2];
                    if (matches(s, p, i, j - 1)) {//匹配s的第i个字符和p的第j-1个字符
                        f[i][j] = f[i][j] || f[i - 1][j];
                    }
                } else {//p的第j个字符不为*
                    if (matches(s, p, i, j)) {//匹配s的第i个字符和p的第j个字符
                        f[i][j] = f[i - 1][j - 1];//匹配成功，状态转移；匹配不成功，默认是false
                    }
                }
            }
        }
        return f[m][n];
    }

    public static boolean matches(String s, String p, int i, int j) {
        if (i == 0) {
            return false;
        }
        if (p.charAt(j - 1) == '.') {
            return true;
        }
        return s.charAt(i - 1) == p.charAt(j - 1);
    }
    
    
    /**
	 * 网友解答
	 * 
	 * 提交结果	执行用时	内存消耗	语言		提交时间				备注 
	 * 通过 		1 ms	36.9 MB	Java	2021/08/20 14:48
	 * 
	 * 执行用时：1 ms, 在所有 Java 提交中击败了100.00%的用户
	 * 内存消耗：36.9 MB, 在所有 Java 提交中击败了85.74%的用户
	 */
    public boolean isMatch3(String s, String p) {
        char[] arrS = s.toCharArray();
        char[] arrP = p.toCharArray();
        int lenS = arrS.length;
        int lenP = arrP.length;
        boolean[][] dp = new boolean[lenS+1][lenP+1];
        dp[0][0]=true;
     
        for(int j=1; j<=lenP; j++) {
            if(arrP[j-1]=='*'){
                dp[0][j] = dp[0][j-2];
            }
        }
        for(int i=1; i<=lenS; i++) {
            for(int j=1; j<=lenP; j++) {
                if(arrP[j-1]=='*') {          
                    if(arrP[j-2]!=arrS[i-1] && arrP[j-2]!='.') {
                        dp[i][j] = dp[i][j-1] || dp[i][j-2];
                    } else{
                        dp[i][j] = dp[i][j-1] || dp[i][j-2] || dp[i-1][j];
                    }
                } 
                else if(arrP[j-1]=='.') {
                    dp[i][j] = dp[i-1][j-1];
                }
                else if(arrP[j-1]==arrS[i-1]){
                    dp[i][j] = dp[i-1][j-1];
                }
                else {
                    dp[i][j] = false;
                }
            }
        }
        return dp[lenS][lenP];
    }
    

	public static void main(String[] args) {
		System.out.print(isMatch("aasdfasdfasdfasdfas",
				"aasdf.*asdf.*asdf.*asdf.*s"));
	}
}
